package com.banmoon.datastructure.HuffmanTree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

@AllArgsConstructor
public class HuffmanTree {

    private Node root;

    public static HuffmanTree generateHuffmanTree(int[] arr) {
        return generateHuffmanTree(Arrays.stream(arr).boxed().toArray(Integer[]::new));
    }

    public static HuffmanTree generateHuffmanTree(Integer[] arr) {
        // 先进行转换
        List<Node> list = Arrays.stream(arr).map(value -> new Node(value)).collect(Collectors.toList());
        // 循环进行
        while (list.size() > 1) {
            // 排序
            list.sort(Comparator.comparingInt(Node::getValue));
            // 取出权值最小的两个节点
            Node left = list.get(0);
            Node right = list.get(1);
            // 创建一个新的节点，作为子树的根节点
            Node parent = new Node(left.getValue() + right.getValue());
            parent.setLeftNode(left);
            parent.setRightNode(right);
            // 将根节点加入数组，删除掉最小的两个节点
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        return new HuffmanTree(list.get(0));
    }

    public void show() {
        if (Objects.nonNull(root))
            root.show();
    }
}

@Data
@NoArgsConstructor
class Node {
    private Integer value;
    private Node leftNode;
    private Node rightNode;

    public Node(Integer value) {
        this.value = value;
    }

    public void show() {
        if (Objects.nonNull(this.value))
            System.out.print(this.value + ",");
        if (Objects.nonNull(this.leftNode))
            this.leftNode.show();
        if (Objects.nonNull(this.rightNode))
            this.rightNode.show();
    }
}